package mryao.tree.AVL;

import mryao.tree.binaryTree;

public class AVLTree extends binaryTree {
    AVLTree() {
        super.root = null;
    }

    AVLTree(int value) {
        super.root = new AVLNode(value);
    }

    public int height(AVLNode node){
        return node == null ? -1 : node.getHeight();
    }

    @Override
    public AVLNode getRoot() {
        return (AVLNode) super.getRoot();
    }

    private AVLNode ll(AVLNode k1){
        AVLNode k2 = (AVLNode) k1.getLeft();
        k1.setLeft(k2.getRight());
        k2.setRight(k1);
        k1.setHeight(Math.max(height((AVLNode) k1.getLeft()),height((AVLNode) k1.getRight())) + 1);
        k2.setHeight(Math.max(height((AVLNode) k2.getLeft()),height((AVLNode) k2.getRight())) + 1);
        return k2;
    }



    private AVLNode RR(AVLNode k1){
        AVLNode k2 =  k1.getRight();
        k1.setRight(k2.getLeft());
        k2.setLeft(k1);
        k1.setHeight(Math.max(height((AVLNode) k1.getLeft()),height((AVLNode) k1.getRight())) + 1);
        k2.setHeight(Math.max(height((AVLNode) k2.getLeft()),height((AVLNode) k2.getRight())) + 1);
        return k2;
    }

    private AVLNode LR(AVLNode k1){
        AVLNode rr = RR(k1);
        return ll(rr);
    }

    private AVLNode RL(AVLNode k1){
        AVLNode ll = ll(k1);
        return RR(ll);
    }

    public void insert (int value){
        if(getRoot() == null){
            setRoot(new AVLNode(value));
        }else {
            setRoot(insertHelp(value, getRoot()));
        }
    }

    private AVLNode insertHelp(int value, AVLNode node){
        if(node == null){
            node = new AVLNode(value);
            return node;
        }
        if (value < node.getData()) {
            node.setLeft(insertHelp(value, node.getLeft()));
            node.setHeight(node.getHeight()+1);
            //判断当前结点在插入后是否失衡
            if (height(node.getLeft()) - height(node.getRight()) == 2) {
                //判断插入的是左还是右
                if (value < node.getData()) {
                    //左左
                    node = ll(node);
                } else {
                    //左右
                    node = LR(node);
                }
            }
        } else if (value > node.getData()) {
            node.setRight(insertHelp(value, node.getRight()));
            node.setHeight(node.getHeight()+1);
            if (height(node.getRight()) - height(node.getLeft()) == 2) {
                if (value < node.getData()) {
                    node = RL(node);
                } else {
                    node = RR(node);
                }
            }
        } else {
            System.out.println(node.getData() + "已经存在");
        }
        node.setHeight(Math.max(height(node.getLeft()), height(node.getRight())) + 1);
        return node;
    }

    //    /**
//     *
//            6
//     5
//                4
//            3
//                2
//                    1
//
//     * @param args 测试ll
//     */
    public static void main(String[] args){
        AVLTree tree = new AVLTree();
        for(int i=0; i< 20 ;i++){
            tree.insert(i);
        }
//        tree.insert(10);
//        tree.insert(4);
//        tree.insert(0);
//        tree.insert(8);
//        tree.insert(3);
//        tree.insert(2);

//        AVLNode n2 = new AVLNode(2);
//        AVLNode n3 = new AVLNode(3);
//        AVLNode n4 = new AVLNode(4);
//        AVLNode n5 = new AVLNode(5);
//        AVLNode n6 = new AVLNode(6);
//        AVLTree tree = new AVLTree();
//        tree.setRoot(n5);
//        n5.setHeight(3);
//        n5.setLeft(n3);
//        n3.setHeight(2);
//        n3.setLeft(n2);
//        n2.setHeight(1);
//        n3.setRight(n4);
//        n4.setHeight(0);
//        n2.setLeft(n1);
//        n5.setRight(n6);
//        n6.setHeight(0);
//        tree.treePrint();
//        tree.setRoot(tree.ll(n5));
        tree.treePrint();
    }

}
